Fibonacci = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,
             28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
             14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170,
             1836311903]
n = int(input())
print(Fibonacci[n])

"""
我很喜欢这道题，这道题其实非常完美全面地展示了数学对优化的作用。
而且这是个绝佳的机会给大家介绍时间复杂度和空间复杂度的概念。
"""
"""
时间/空间复杂度，即程序运行时间/程序占用空间随问题规模膨胀的速度。（注：以下所有的）
比如，如果用最传统的循环递推方法，我们求出斐波那契数列的第n位需要一个n次循环。换句话说，我们需要的时间正比于n，所以时间复杂度记为Θ(n)。
与此同时，如果我们依次把斐波那契数列的每一位都记下来，那么我们要记录的数据正比于n，所以空间复杂度记为Θ(n)。
当然，事实上我们可以在循环到i次的时候，只用变量记录i-2,i-1两位，然后不断地覆写来节约空间，这样我们需要的空间不随n增加而增加，是一个常数，记为Θ(1)。
你会发现严格来说，程序占用的时间和空间应该是复杂度乘一个常数。但是我们一般不太在乎那个常数是什么。
因为即便是个人计算机，一秒也起码可以进行上亿次基本计算。这意味着当我们能够感觉到这个程序太慢了，想要让他更快的时候，计算规模已经至少是10^8量级了
比如一个用时1s的，O(n^2)的算法，意味着问题规模n≈10^4。如果你能把它简化到Θ(nlog2(n))，就快了近千倍，根本不是常数上一点小小的变化能相比的。
当然这些都是理论上，其实还有各式各样的东西需要花费时间和空间。
比如查阅提交报告你会发现即便是1.1.1这样简单的程序也要花相当多，不知道拿去干嘛了的时间和空间。
但是一般来说，等到你已经能感觉到它太慢了/占用空间太大了，需要想办法改进的时候，复杂度就是你首先需要分析的东西。
"""
"""
这道题我计划用三种不同的算法实现，这里是第一种——打表法
它的时间复杂度为Θ(1)，空间复杂度为Θ(n)
打表法是一种看似很蠢其实非常高明的做法。我希望大家不要对他有偏见。它最大的优点就是几乎无可替代地快。
对于一些可能需要重复运行的程序大家甚至经常会用另一个程序来生成表，这样以后就可以一劳永逸地打表了。
比方说这个表就是我用以下程序打出来的：
# 打完复制粘贴到括号里，更聪明的做法是直接打印到一个外部文件，然后从外部调用这个list，可惜大部分OJ不允许外部调用
a = 0
b = 1
print("0, 1, ", end='')
for i in range(45):
    print(a + b, end=', ')
    c = a
    a = b
    b = c + b
"""
